/**********************************************************

@description:
*File Name:graph.c
*Author: ydx
*mail: yudongxiang93@163.com
*Create Time: Wed 30 Apr 2025 10:53:12 PM CST
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "queue.h"
typedef struct graph{
	char *vexs;
	int **arcs;
	int vex_num,arc_num;
}graph;

graph * init_graph(int vex_num){
	graph *g=(graph*)malloc(sizeof(graph));
	g->vexs=(char*)malloc(sizeof(char)*vex_num);
	g->arcs=(int**)malloc(sizeof(int*)*vex_num);
	for(int i=0;i<vex_num;i++){
		g->arcs[i]=(int*)malloc(sizeof(int)*vex_num);
	}
	g->vex_num=vex_num;
	g->arc_num=0;
	return g;
}
void createGraph(graph *g,char *vexs,int* arcs){
	for(int i=0;i<g->vex_num;i++){
		g->vexs[i]=vexs[i];
		for(int j=0;j<g->vex_num;j++){
			g->arcs[i][j]=*(arcs+i*g->vex_num+j);
			if(g->arcs[i][j] != 0){
				g->arc_num++;
			}
		}
	}
	g->arc_num/=2;
}
void bfs(graph *g,int* visited,int index){
	queue *q=init_queue();
	printf("%c\t",g->vexs[index]);
	visited[index]=1;
	enqueue(q,index);
	while(!isEmpty(q)){
		int i=dequeue(q);
		for(int j=0;j<g->vex_num;j++){
			if(g->arcs[i][j]==1 && !visited[j]){
				printf("%c\t",g->vexs[j]);
				visited[j]=1;
				enqueue(q,j);
			}

		}
	}

}
void dfs(graph *g,int* visited,int index){
	printf("%c\t",g->vexs[index]);
	visited[index]=1;
	for(int i=0;i<g->vex_num;i++){
		if(g->arcs[index][i]==1 && !visited[i]){
			dfs(g,visited,i);
		}
	}
}
int main(){
	graph* g=init_graph(5);
	int arcs[25]={
		0,1,1,1,0,
		1,0,1,1,1,
		1,1,0,0,0,
		1,1,0,0,1,
		0,1,0,1,0,
	};
	createGraph(g,"ABCDE",arcs);

	printf("dfs:");
	int *visited=(int*)malloc(sizeof(int)*g->vex_num);
	memset(visited,0,g->vex_num*sizeof(int));
	dfs(g,visited,0);
	printf("\nqueu tst:");
	int arr[6]={11,12,13,14,15,16};
	queue *q=init_queue();
	for(int i=0;i<6;i++){
		enqueue(q,arr[i]);
	}
	while(!isEmpty(q)){
		printf("%d\t",dequeue(q));
	}
	printf("\nbfs:");
	memset(visited,0,g->vex_num*sizeof(int));
	bfs(g,visited,0);
	printf("\n");
	
}
